{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "## Открытый курс по машинному обучению\n",
    "<center>Автор материала: Измайлов Константин Константинович (@Izmajlovkonstantin)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  <center>Отбор признаков с помощью алгоритма Boruta или как приручить лесного демона. <BR> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://raw.githubusercontent.com/Twoweaks/random/master/leshyboruta12.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Введение"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Решая ту или иную задачу машинного обучения не стоит забывать одно простое правило: <I>\"Garbage in - garbage out\" </I>, означающее, что чем \"зашумленнее\" были поданы данные на входе, тем хуже будет решение задачи.\n",
    "\n",
    "Корректный отбор признаков - один из важнейших этапов предобработки данных. Особенно критичен отбор признаков при решении задач в индустрии, когда датасаентист встречается с большим набором фичей, многие из которых не имеют отношения к решаемой проблеме.\n",
    "\n",
    "Отбор признаков обеспечаивает следующие преимущества:\n",
    "<UL>\n",
    "<LI> уменьшение переобучения;\n",
    "<LI> повышение точности;\n",
    "<LI> сокращение времени обучения;\n",
    "<LI> сокращение затрат на поиск и обновление информации (характерно для индустрии).    \n",
    "</UL>\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Существуют три основных класса алгоритмов отбора признаков:\n",
    "<OL>\n",
    "<LI> <B> Фильтры </B> - применяются до классификации, не зависят от алгоритма самой модели. Признаки отбираются, как правило, основываясь на оценках статистических тестов (корреляци Пирсона, LDA, ANOVA и т.д.);\n",
    "<LI> <B> Встроенные методы </B> - выполняют отбор признаков неотделимо от процесса обучения модели (наприм. - Lasso-регрессия); \n",
    "<LI> <B> Оберточные методы </B> - используют информацию о важности признаков, полученную от алгоритмов обучения, и затем находят сложные зависимости между ними. \n",
    "</OL>    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Схематичное изображение оберточного метода.\n",
    "<img src=\"https://raw.githubusercontent.com/Twoweaks/random/master/Wrapper_1.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Одним из таких оберточных методов, который будет рассмотрен в данном туториале, будет алгоритм <B> Boruta </B>, названный в честь лесного славянского демона, реализующий адаптационный алгоритм для модели случайного леса (Kursa, Rudnicki, 2010)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Алгоритм Boruta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Основная идея алгоритма заключается в сравнении исходных признаков с их теневыми копиями (англ. - shadow features) - признаками, полученными с помощью случайного перемешивания значений исходных признаков между строками. Соответственно, признаки, которые мало чем отличаются от теневых будут совершенно не важны для модели.   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<U>Рассмотрим алгоритм пошагово:</U>\n",
    "<OL>\n",
    "    <LI> Добавить в исходный набор данных теневые копии всех признаков (обычно добавляется по 5 теневых признаков для каждого признака исходного набора данных, вне зависимости от их общего числа);\n",
    "    <LI> Обучить несколько раз алгоритм (в данном случае - случайный лес) на новом наборе данных;\n",
    "    <LI> Рассчитать важность всех признаков на каждой итерации алгоритма.\n",
    "    Важность признаков рассчитывается как дополнительная ошибки регрессии, вызванная исключением этого признака из модели. Среднее  $μ$  этой дополнительной ошибки и его стандартное отклонение $σ$ рассчитываются по всем деревьям в лесу, которые используют оцениваемый признак для прогнозирования. Мера $Z$ каждого признака рассчитывается как  $\\dfrac{μ}{σ}$. Данная оценка не может использоваться напрямую для определения важности каждого из признаков модели в отдельности, так как не имеет нормального распределения. \n",
    "        <BR>\n",
    "     <LI> Для каждого из признаков с помощью биноминального распределения подсчитывается, какая вероятность того, что $Z$-мера исходного признака будет выше $Z$-меры всех его теневых признаков. Рассчитывается уровень значимости $p$ с поправкой на множественную проверку гипотез (для алгоритма Boruta используется достаточно консервативная коррекция Бонфферони), так как такое сравнение делается для тысячи итераций;\n",
    "       <LI> Признаки, у которых веротяность $Z$-меры теневых признаков статистически значима выше вероятности $Z$-меры исходного признака считаются неважными и выбрасываются из обучаемого набора данных (зачастую со своими теневыми копиями);\n",
    "        <LI> Процедура повторяется до тех пор, пока не будет достигнут заданный набор итераций или всем признаком не будет проставлен признак важности.\n",
    "</OL>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Интерфейс алгоритма"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Изначально алгоритм был реализован на R, а уже затем перенесен на Python с некоторыми изменениями:\n",
    "<UL>\n",
    "    <LI> поправка на множественную проверку гипотез стала более лояльной, но осталась возможность использовать коррекцию Бонфферони (задается опционально через параметр алгоритма <I> two_step  </I>);\n",
    "    <LI> скорректировано сравнение признаков с их теневыми копиями, в новой реализации учитываются перцентили, вместо строгого количественного сравнения в оригинальном алгоритме;\n",
    "        <LI> в том числе оптимизирована работа алгоритма, увеличено его бытсродействие и стабильность, добавлена совместимость с любым ансамблевым методом из sklearn.\n",
    "    </UL>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<U> Параметры алгоритма: </U>\n",
    "<B>estimator</B> : object \n",
    "<B>n_estimators </B> : int or string, default = 1000 \n",
    "<B>perc</B> : int, default = 100 \n",
    "<B>alpha </B> : float, default = 0.05 \n",
    "<B>two_step </B>  : Boolean, default = True \n",
    "<B>max_iter</B>  : int, default = 100 \n",
    "<B>verbose </B>  : int, default=0 \n",
    "\n",
    "Более подробно о параметрах и атрибутах можно прочитать [тут](https://github.com/scikit-learn-contrib/boruta_py)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Пример реализации"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Применять алгоритм Boruta будем на публичном датасете <I>  Breast Cancer Wisconsin (Diagnostic) Data Set </I> представляющий собой проблему классификации, где по характеристикам опухоли в женской груди необходимо определить, является ли опухоль доброкачественной (benign) либо злокачественной (malignant). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# импортируем необходимые библиотеки\n",
    "import warnings\n",
    "\n",
    "warnings.filterwarnings('ignore')\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from boruta import BorutaPy\n",
    "#загружаем сам датасет\n",
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.metrics import roc_auc_score\n",
    "from sklearn.model_selection import StratifiedKFold\n",
    "\n",
    "data = load_breast_cancer()\n",
    "\n",
    "df = pd.DataFrame(np.c_[data['data'], data['target']],\n",
    "                  columns= np.append(data['feature_names'], ['target']))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Датасет состоит из 30 признаков и одного целевого признака. О значении большинства признаков остается лишь догадываться, тем более определить их значимость, датасаентисту, не разбирающемуся в медицине, не представляется возможным."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Доля меток с злокачественной опухолью - {}.'.format(np.round(df[df.target == 1].shape[0]/df.shape[0],2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Валидировать алгоритм будем на 3 фолдах, в качестве метрики будем использовать ROC AUC score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = df.iloc[:,:-1]\n",
    "y = df['target']\n",
    "\n",
    "def validation(ensemble, X, y, n_folds = 3):\n",
    "    rocs = []\n",
    "    skf = StratifiedKFold(n_splits=n_folds)\n",
    "    for train, test in skf.split(X, y):\n",
    "        X_train, X_test = X.loc[train,:], X.loc[test,:]\n",
    "        y_train, y_test = y[train],y[test]\n",
    "        ensemble.fit(X_train,y_train)      \n",
    "        rocs.append(roc_auc_score(y_test,ensemble.predict_proba(X_test)[:,1]))\n",
    "    return np.mean(rocs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Воспользуемся коробочным решением алгоритма и посмотрим на результат."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = RandomForestClassifier(n_estimators=500,max_depth=3, random_state=10)\n",
    "print('ROC AUC SCORE - {}.'.format(validation(clf, X, y)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Коробочное решение алгоритма справляется уже неплохо, попробуем призвать нашего лесного демона, может, он сможет улучшить наш алгоритм. При этом, попробуем добавить в данные немного шума, посмотрим, сможет ли Boruta найти их. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_with_noise = X.copy()\n",
    "X_with_noise['random_noise_0'] = np.random.random( X_with_noise.shape[0])\n",
    "X_with_noise['random_noise_1'] = np.random.random( X_with_noise.shape[0])\n",
    "X_with_noise['random_noise_2'] = np.random.random( X_with_noise.shape[0])\n",
    "X_with_noise['random_noise_3'] = np.random.random( X_with_noise.shape[0])\n",
    "\n",
    "feat_selector = BorutaPy(clf, n_estimators='auto', verbose=2, random_state=17, max_iter=50)\n",
    "feat_selector.fit(X_with_noise.values, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Уже на 8 итерации Boruta определил 4 добавленных шумовых признака. В том числе, для некоторых признаков исходного датасета была поставлена метка <I>Tentative</I>, то есть алгоритм не совсем уверен, являются ли данные метки важными для предсказания или нет. \n",
    "\n",
    "Определим, что это за признаки и попробуем обучить алгоритм без них."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Неважные для обучения признаки\n",
    "X_with_noise.columns[np.where(feat_selector.ranking_ !=1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_important = X.iloc[:,np.where(feat_selector.ranking_ ==1)[0]]\n",
    "clf = RandomForestClassifier(n_estimators=500,max_depth=3, random_state=10)\n",
    "print('ROC AUC SCORE - {}.'.format(validation(clf, X_important, y)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Качество алгоритма улучшилось! А значит, наш лесной демон выполнил свою работу и может отправляться обратно в лес."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Заключение"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хоть и в данном примере Boruta отработал на отлично, и с его помощью удалось улучшить качество алгоритма, но это не всегда так. В любом случае, попробовать использовать алгоритм стоит.\n",
    "\n",
    "Стоит отметить, что у алгоритма есть небольшой баг, который автор еще не устранил:\n",
    "в том случае, если по завершению всех итераций алгоритма Boruta не нашёл ни одного неважного признака (Rejected = 0) вылетает ошибка <B>\"iteration over a 0-d array\"</B>. До выхода нового апдейта модуля для корректной работы алгоритма можно добавлять колонку констант, которая будет наверняка принята алгоритмом как rejected и не спровоцирует вышеобознаечнную ошибку. \n",
    "\n",
    "По личному опыту скажу, что Boruta хорошо заходит в задачах с генерацией большого количества искусственных признаков: в задачах кредитного скоринга, но не стоит забывать, что работа алгоритма может занять много времени в зависимости от объема данных. \n",
    "\n",
    "Также в сети появилась новая улучшенная версия Boruta, реализованная на всеми любимом XGBoost. Прочитать про нее можно [тут](https://github.com/chasedehan/BoostARoota).\n",
    "\n",
    "На последок, желаю всем успехов в тренировки своих демонов, надеюсь данный туториал был вам полезен!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://raw.githubusercontent.com/Twoweaks/random/master/i_006.png\" width=\"400\">"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
